Thuật toán Thuật_toán_Edmonds–Karp

Cấu trúc của thuật toán giống hệt như thuật toán Ford–Fulkerson, chỉ khác cách lựa chọn đường tăng luồng. Đường tăng luồng được chọn là đường tăng có ít cung nhất. Có thể tìm đường tăng này bằng tìm kiếm theo chiều rộng. Có thể chứng minh thời gian chạy của thuật toán là O(VE2) như sau. Thời gian để tìm mỗi đường tăng là O(E). Sau mỗi lần tăng luồng, ít nhất một cung của đồ thị trở thành bão hòa. Mỗi lần một cung trong E trở nên bão hòa (một cung có thể trở thành bão hòa nhiều lần), khoảng cách từ nguồn tới cung bị bão hòa tăng lên ít nhất 1 so với lần cuối cùng nó bị bão hòa trước đó. Khoảng cách này không bao giờ vượt quá V. Một tính chất nữa là khoảng cách từ nguồn tới một đỉnh bất kì là không giảm trong suốt quá trình tăng luồng. Có thể tham khảo một chứng minh đơn giản cho tính chất này ở Cormen và đồng nghiệp (2001)Lỗi harv: không có mục tiêu: CITEREFCormenLeisersonRivestStein2001 (trợ giúp). Như vậy số lần tăng luồng là không quá O(VE) và thời gian chạy là O(VE2).